package gold.digger;

import java.util.ArrayList;
import java.util.*;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC115 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int numDistinct(String s, String t) {
            if (t.length() <= 0) return 1;
            if (s.length() < t.length()) return 0;

            int[][] dp = new int[s.length()][t.length()];
            Map<Character, List<Integer>> dict = new HashMap<>();
            int firstSameCount = 0;
            for (int i = 0; i < s.length(); i++) {
                firstSameCount += s.charAt(i) == t.charAt(0) ? 1 : 0;
                dp[i][0] = firstSameCount;
                char ch = s.charAt(i);
                if (dict.containsKey(ch)) {
                    dict.get(ch).add(i);
                } else {
                    dict.put(ch, new ArrayList<>(Arrays.asList(i)));
                }
            }

            for (int j = 1; j < t.length(); j++) {
                char tChar = t.charAt(j);
                List<Integer> sIdxList = dict.get(tChar);
                if (null == sIdxList) return 0;
                for (int i = j; i < s.length(); i++) {
                    for (Integer sIndex : sIdxList) {
                        if (sIndex > i) break;
                        if (j > sIndex) continue;
                        dp[i][j] += dp[sIndex - 1][j - 1];
                    }
                }
            }

            return dp[s.length() - 1][t.length() - 1];
        }
    }

    public void run() {
        Solution solution = new Solution();
        System.out.println(solution.numDistinct("", "a"));
    }

    public static void main(String[] args) throws Exception {
        LC115 an = new LC115();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
